{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reverse Substrings Between Each Pair of Parentheses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reverseParentheses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #反转每对括号间的子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给出一个字符串&nbsp;<code>s</code>（仅含有小写英文字母和括号）。</p>\n",
    "\n",
    "<p>请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。</p>\n",
    "\n",
    "<p>注意，您的结果中 <strong>不应</strong> 包含任何括号。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"(abcd)\"\n",
    "<strong>输出：</strong>\"dcba\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"(u(love)i)\"\n",
    "<strong>输出：</strong>\"iloveu\"\n",
    "<strong>解释：</strong>先反转子字符串 \"love\" ，然后反转整个字符串。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"(ed(et(oc))el)\"\n",
    "<strong>输出：</strong>\"leetcode\"\n",
    "<strong>解释：</strong>先反转子字符串 \"oc\" ，接着反转 \"etco\" ，然后反转整个字符串。</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"a(bcdefghijkl(mno)p)q\"\n",
    "<strong>输出：</strong>\"apmnolkjihgfedcbq\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 2000</code></li>\n",
    "\t<li><code>s</code> 中只有小写英文字母和括号</li>\n",
    "\t<li>题目测试用例确保所有括号都是成对出现的</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reverse-substrings-between-each-pair-of-parentheses](https://leetcode.cn/problems/reverse-substrings-between-each-pair-of-parentheses/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reverse-substrings-between-each-pair-of-parentheses](https://leetcode.cn/problems/reverse-substrings-between-each-pair-of-parentheses/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"(abcd)\"', '\"(u(love)i)\"', '\"(ed(et(oc))el)\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        if not s:\n",
    "            return \"\"\n",
    "        word = ''\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                stack.append(word)\n",
    "                word = ''\n",
    "            elif c == ')':\n",
    "                word = stack.pop() + word[::-1]\n",
    "            else:\n",
    "                word += c\n",
    "        return word\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    obj = Solution()\n",
    "    s = \"(u(love)i)\"\n",
    "    print(obj.reverseParentheses(s))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        ans = \"\"\n",
    "        count = []\n",
    "        num = 0\n",
    "        for i in s:\n",
    "            if i.isalpha()==True and num == 0:\n",
    "                ans += i\n",
    "            elif i=='(':\n",
    "                count.append(\"\")\n",
    "                num += 1\n",
    "            elif i.isalpha()==True and num>0:\n",
    "                count[-1] += i\n",
    "            elif i==')':\n",
    "                num -= 1\n",
    "                if num == 0:\n",
    "                    ans += count[-1][::-1]\n",
    "                else:\n",
    "                    a = count.pop()[::-1]\n",
    "                    count[-1] += a  \n",
    "        return ans\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        res = ''\n",
    "        stack = []\n",
    "        for i in s:\n",
    "            if i.isalpha():\n",
    "                res += i\n",
    "            elif i =='(':\n",
    "                stack.append(res)\n",
    "                res = ''\n",
    "            elif i == ')':\n",
    "                res = stack[-1] + res[::-1]\n",
    "                stack.pop()\n",
    "            else:\n",
    "                pass\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        ss = []\n",
    "        for i in s:\n",
    "            if i != \")\":\n",
    "                ss.append(i)\n",
    "            else :\n",
    "                sss = []\n",
    "                while len(ss) > 0 :\n",
    "                    x = ss.pop()\n",
    "                    if x != \"(\":\n",
    "                        sss.append(x)\n",
    "                    else :\n",
    "                        ss += sss\n",
    "                        break\n",
    "        ans = \"\".join(ss)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "letterRegex = re.compile('([a-z])')\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, a, r):\n",
    "        if r:\n",
    "            a = reversed(a)\n",
    "        r = not r\n",
    "        for x in a:\n",
    "            if type(x) is str:\n",
    "                self.res.append(x)\n",
    "            else:\n",
    "                self.dfs(x, r)\n",
    "\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        self.res = []\n",
    "        self.dfs(eval('(%s)' % letterRegex.sub(r\"'\\1',\", s).replace(')', '),')), False)\n",
    "        return ''.join(self.res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        result = s\n",
    "        stack = []\n",
    "        for index, c in enumerate(s):\n",
    "            if c == '(':\n",
    "                stack.append(index)\n",
    "            elif c == ')':\n",
    "                # reverse sub string\n",
    "                start = stack.pop()\n",
    "                result = result[:start] + result[start:index][::-1] + result[index:]\n",
    "            else:\n",
    "                pass\n",
    "        return result.replace('(', '').replace(')', '')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stack = []\n",
    "        for ch in s:\n",
    "            if ch != \")\":\n",
    "                stack.append(ch)\n",
    "            else:\n",
    "                sen = []\n",
    "                while stack[-1] != \"(\":\n",
    "                    sen += stack.pop()\n",
    "                stack.pop()\n",
    "                stack += sen\n",
    "        return \"\".join(stack)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stack = []\n",
    "        for i in s:\n",
    "            if i != ')':\n",
    "                stack.append(i)\n",
    "            elif i == ')':\n",
    "                temp = []\n",
    "                while stack and stack[-1] != '(':\n",
    "                    temp.append(stack.pop())\n",
    "                if stack:\n",
    "                    stack.pop()\n",
    "                stack += temp\n",
    "        return ''.join(stack)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stack=[]\n",
    "        res=''\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in ['(',')']:\n",
    "                if len(stack):\n",
    "                    stack[-1]+=s[i]\n",
    "                else:\n",
    "                    res+=s[i]\n",
    "            elif s[i]=='(':\n",
    "                stack.append('')\n",
    "            else:\n",
    "                tmp=stack[-1][::-1]\n",
    "                stack.pop()\n",
    "                if len(stack):\n",
    "                    stack[-1]+=tmp\n",
    "                else:\n",
    "                    res+=tmp\n",
    "        return res\n",
    "\n",
    "    #     def dfs(idx)-> str:\n",
    "    #         tmp=''\n",
    "    #         i=idx\n",
    "    #         while i<len(s):\n",
    "    #             if s[i] not in ['(',')']:\n",
    "    #                 tmp+=s[i]\n",
    "    #                 i+=1\n",
    "    #             elif s[i] == '(':\n",
    "    #                 ba=dfs(i+1)\n",
    "    #                 tmp+=ba\n",
    "    #                 i+=len(ba)\n",
    "    # #                 print(i)\n",
    "    #             else:\n",
    "    # #                 print(tmp)\n",
    "    #                 return '('+tmp[::-1]+')'\n",
    "    #         return tmp\n",
    "    #     res=dfs(0)\n",
    "    #     res1=''\n",
    "    #     for i in range(len(res)):\n",
    "    #         res1+=res[i] if res[i] not in ['(',')'] else ''\n",
    "    #     return res1\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if c != ')':\n",
    "                stack.append(c)\n",
    "            elif c == ')':\n",
    "                tmp = []\n",
    "                while stack and stack[-1] != '(':\n",
    "                    tmp.append(stack.pop())\n",
    "                if stack: # 等于(时\n",
    "                    stack.pop()\n",
    "                stack += tmp\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        d = dict()\n",
    "        stack = []\n",
    "        for i in range(len(s)):\n",
    "            if(s[i] == \"(\"):\n",
    "                stack.append(i)\n",
    "            elif(s[i] == \")\"):\n",
    "                leftIndex = stack.pop()\n",
    "                d[leftIndex] = i\n",
    "                d[i] = leftIndex \n",
    "        index = 0\n",
    "        dirc = 1\n",
    "        ans = \"\"\n",
    "        while(index >= 0 and index < len(s)):\n",
    "            if(s[index] == \"(\" and dirc == 1):\n",
    "                index = d[index] - 1\n",
    "                dirc = -1\n",
    "            elif(s[index] == \")\" and dirc == -1):\n",
    "                index = d[index] + 1\n",
    "                dirc = 1\n",
    "            elif(s[index] == \")\" and dirc == 1):\n",
    "                index = d[index] - 1\n",
    "                dirc = -1\n",
    "            elif(s[index] == \"(\" and dirc == -1):\n",
    "                index = d[index] + 1\n",
    "                dirc = 1\n",
    "            else:\n",
    "                ans += s[index]\n",
    "                index = index + dirc\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        ans = ['']\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                ans += ['']\n",
    "            elif c == ')':\n",
    "                ans[-2] += ans[-1][::-1]\n",
    "                ans.pop()\n",
    "            else:\n",
    "                ans[-1] += c\n",
    "        return ans[-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stack = []\n",
    "        cur_str = ''\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                stack.append(cur_str)\n",
    "                cur_str = ''\n",
    "            elif c == ')':\n",
    "                cur_str = stack.pop() + cur_str[::-1]\n",
    "            else:\n",
    "                cur_str += c\n",
    "        return cur_str\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        st = []\n",
    "        for ch in s:\n",
    "            if ch !=\")\":\n",
    "                st.append(ch)\n",
    "            else:\n",
    "                temp = \"\"\n",
    "                while st and st[-1] != \"(\":\n",
    "                    temp += st.pop()\n",
    "                st.pop()\n",
    "                for i in temp:\n",
    "                    st.append(i)\n",
    "        return \"\".join(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stack = []\n",
    "        for word in s:\n",
    "            if word != ')':\n",
    "                stack.append(word)\n",
    "            else:\n",
    "                tmp=[]\n",
    "                while stack[-1]!='(':\n",
    "                    tmp.append(stack[-1])\n",
    "                    stack.pop()\n",
    "                stack.pop()\n",
    "                stack+=tmp\n",
    "        return \"\".join(stack)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        res = []\n",
    "        for ch in s:\n",
    "            if ch != ')':\n",
    "                res.append(ch)\n",
    "            elif ch == ')':\n",
    "                tmp = []\n",
    "                while res and res[-1] != '(':\n",
    "                    tmp.append(res.pop())\n",
    "                res.pop()\n",
    "                res += tmp\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stack = []\n",
    "        res = []\n",
    "        for i in s:\n",
    "            # print(i)\n",
    "            # print(stack)\n",
    "            if i == \")\":\n",
    "                for l in range(len(stack)-1, -1, -1):\n",
    "                    # print(l)\n",
    "                    if stack[l] != \"(\":\n",
    "                        res.append(stack.pop())\n",
    "                    else:\n",
    "                        stack.pop()\n",
    "                        break\n",
    "                for r in res:\n",
    "                    stack.append(r)\n",
    "                    res = []\n",
    "            else:\n",
    "                stack.append(i)\n",
    "        # print(stack)\n",
    "        # print(res)\n",
    "        ans = \"\"\n",
    "        for st in stack:\n",
    "            ans += st\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if c != ')':\n",
    "                stack.append(c)\n",
    "            elif c == ')':\n",
    "                tmp = []\n",
    "                while stack and stack[-1] !='(':\n",
    "                    tmp.append(stack.pop())\n",
    "                if stack:\n",
    "                    stack.pop()\n",
    "                stack += tmp\n",
    "        return \"\".join(stack)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        if not s:\n",
    "            return \"\"\n",
    "        word = \"\"\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if c == \"(\":\n",
    "                stack.append(word)\n",
    "                word = \"\"\n",
    "            elif c == \")\":\n",
    "                word = stack.pop() + word[::-1]\n",
    "            else:\n",
    "                word += c\n",
    "        return word\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    obj = Solution()\n",
    "    s = \"(u(love)i)\"\n",
    "    print(obj.reverseParentheses(s))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stack = []\n",
    "        Indexlist = []\n",
    "        for i in range(len(s)):\n",
    "            Str = s[i]\n",
    "            if Str.isalpha():\n",
    "                stack.append(Str)\n",
    "\n",
    "            elif Str == '(':\n",
    "                Indexlist.append(len(stack))\n",
    "\n",
    "            elif Str == ')':\n",
    "                lastIndex = Indexlist.pop()\n",
    "                stack[lastIndex:] = stack[lastIndex:][::-1]\n",
    "\n",
    "        return \"\".join(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stk = []\n",
    "        n = len(s)\n",
    "        idx, prev = 0, 0\n",
    "        while idx < n:\n",
    "            if s[idx].isalpha():\n",
    "                idx += 1\n",
    "                continue\n",
    "            stk.append(s[prev:idx])\n",
    "            if s[idx] == \"(\":\n",
    "                stk.append(s[idx])\n",
    "            else:\n",
    "                tmp = []\n",
    "                while stk[-1] != \"(\":\n",
    "                    tmp.append(stk.pop())\n",
    "                stk.pop()\n",
    "                stk.append(\"\".join(tmp[::-1])[::-1])\n",
    "            idx += 1\n",
    "            prev = idx\n",
    "        stk.append(s[prev:idx])\n",
    "        return \"\".join(stk)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stk = []\n",
    "        n = len(s)\n",
    "        tmpStr = \"\"\n",
    "        for ch in s:\n",
    "            if ch == \"(\":\n",
    "                stk.append(tmpStr)\n",
    "                tmpStr = \"\"\n",
    "            elif ch == \")\":\n",
    "                tmpStr = stk[-1] + tmpStr[::-1]\n",
    "                stk.pop()\n",
    "            else:\n",
    "                tmpStr += ch\n",
    "        return tmpStr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        s_stack, word = [], \"\"\n",
    "        for c in s:\n",
    "            if c in \"(\":\n",
    "                s_stack.append(word)\n",
    "                word = \"\"\n",
    "            elif c in \")\":\n",
    "                word = s_stack.pop() + word[::-1]\n",
    "            else:\n",
    "                word += c\n",
    "        return word"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stack = []\n",
    "\n",
    "        for elem in s:\n",
    "            if elem == ')':\n",
    "                tmp = []\n",
    "\n",
    "                while stack[-1] != '(':\n",
    "                    tmp.append(stack.pop())\n",
    "\n",
    "                stack.pop()\n",
    "                stack.extend(tmp)\n",
    "\n",
    "            else:\n",
    "                stack.append(elem)\n",
    "\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        inner = \"\"\n",
    "        full = \"\"\n",
    "        stack = []\n",
    "        for ch in s:\n",
    "            if ch == '(':\n",
    "                stack.append(inner)\n",
    "                inner = \"\"\n",
    "            elif ch == ')':\n",
    "                inner = inner[::-1]\n",
    "                stack[-1] += inner\n",
    "                inner = stack.pop()\n",
    "            else:\n",
    "                inner = inner + ch\n",
    "        return inner"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        statck = []\n",
    "        for tmp_str in s:\n",
    "            if tmp_str==\")\":\n",
    "                s1 = []\n",
    "                while statck[-1]!=\"(\":\n",
    "                    s2 = statck.pop()\n",
    "                    s1.append(s2)\n",
    "                statck.pop()\n",
    "                statck.extend(s1)\n",
    "            else:\n",
    "                statck.append(tmp_str)\n",
    "        print(statck)\n",
    "        return \"\".join(statck)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "\n",
    "        p=[]\n",
    "        lists=[]\n",
    "        for i in s:\n",
    "            if i=='(':\n",
    "                p.append(len(lists))\n",
    "                lists.append(i)\n",
    "            elif i==')':\n",
    "                temp=p.pop()\n",
    "                temp1=''.join(lists[temp+1:])[::-1]\n",
    "                lists=lists[:temp]\n",
    "                lists.append(temp1)\n",
    "            else:\n",
    "                lists.append(i)\n",
    "        return''.join(lists)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stack=[]\n",
    "        for c in s:\n",
    "            if c!=')':stack.append(c)\n",
    "            elif c==')':\n",
    "                temp=[]\n",
    "                while stack and stack[-1]!='(':\n",
    "                    temp.append(stack.pop())\n",
    "                stack.pop() # 去除左括号\n",
    "                stack+=temp\n",
    "        return ''.join(stack)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stack = []\n",
    "        for i in s:\n",
    "            if i !=')':\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                tmp = []\n",
    "                while stack and stack[-1]!='(':\n",
    "                    tmp.append(stack.pop())\n",
    "                if stack:\n",
    "                    stack.pop()\n",
    "                stack+= tmp\n",
    "        a = \"\".join(stack)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        ans = \"\"\n",
    "        count = []\n",
    "        num = 0\n",
    "        for i in s:\n",
    "            if i.isalpha()==True and num == 0:\n",
    "                ans += i\n",
    "            elif i=='(':\n",
    "                count.append(\"\")\n",
    "                num += 1\n",
    "            elif i.isalpha()==True and num>0:\n",
    "                count[-1] += i\n",
    "            elif i==')':\n",
    "                num -= 1\n",
    "                if num == 0:\n",
    "                    ans += count[-1][::-1]\n",
    "                else:\n",
    "                    a = count.pop()[::-1]\n",
    "                    count[-1] += a  \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        pattern = re.compile(r'\\((?=(\\w*))\\1\\)')\n",
    "        while '(' in s:\n",
    "            s = pattern.sub(lambda m:m.group(1)[::-1], s)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s):\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if c != ')':\n",
    "                stack.append(c)\n",
    "            elif c == ')':\n",
    "                temp=[]\n",
    "                # 注意stack不为空才可以读取栈顶\n",
    "                while stack and stack[-1] != '(':\n",
    "                    temp.append(stack.pop())\n",
    "                if stack:\n",
    "                    stack.pop() # 将左括号抛出\n",
    "                stack += temp\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        stk = list()\n",
    "        for i in range(n):\n",
    "            if s[i] != ')':\n",
    "                stk.append(s[i])\n",
    "            elif s[i] == ')':\n",
    "                temp = list()\n",
    "                while stk and stk[-1] != '(':\n",
    "                    temp.append(stk.pop())\n",
    "                if stk:\n",
    "                    stk.pop()\n",
    "                stk += temp\n",
    "        return \"\".join(stk)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        string = ''\n",
    "        stuck = []\n",
    "        for i in s:\n",
    "            if i == '(':\n",
    "                stuck.append(string)\n",
    "                string = ''\n",
    "                # enter next level\n",
    "                #self.reverseParentheses(s)\n",
    "            elif i == ')':\n",
    "                string = string[::-1]\n",
    "                string = stuck.pop() + string\n",
    "                #print(string)\n",
    "            else:\n",
    "                string += i\n",
    "        return string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        while '(' in s:\n",
    "            s = re.sub(r'\\((?=(\\w*))\\1\\)', lambda m:m.group(1)[::-1], s)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if c == ')':\n",
    "                temp = []\n",
    "                while stack and stack[-1] != '(':\n",
    "                    temp.append(stack.pop())\n",
    "                if stack[-1] == '(':\n",
    "                    stack.pop()\n",
    "                stack.extend(temp)\n",
    "            else:\n",
    "                stack.append(c)\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        st = []\n",
    "        tmp = \"\"\n",
    "        for si in s:\n",
    "            if si.islower() or si == '(':\n",
    "                st.append(si)\n",
    "            elif si == ')':\n",
    "                # print(st)\n",
    "                tmp = \"\"\n",
    "                while st[-1] != '(':\n",
    "                    tmp += st.pop()\n",
    "                st.pop()\n",
    "                # print(tmp)\n",
    "                for pi in tmp:\n",
    "                    st.append(pi)\n",
    "        return (\"\".join(st))\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if c != ')':\n",
    "                stack.append(c)\n",
    "            elif c == ')':\n",
    "                tmp = []\n",
    "                while stack and stack[-1] != '(':\n",
    "                    tmp.append(stack.pop())\n",
    "                if stack:\n",
    "                    stack.pop() # 将左括号抛出\n",
    "                stack += tmp\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stackFirst = []\n",
    "        i = 1\n",
    "        stackSecd = [s[0]]\n",
    "        while i < len(s):\n",
    "            if s[i] == \")\":\n",
    "                while stackSecd[-1] != \"(\":\n",
    "                    stackFirst.append(stackSecd[-1])\n",
    "                    del stackSecd[-1]\n",
    "                del stackSecd[-1]\n",
    "\n",
    "                while len(stackFirst) != 0:\n",
    "                    stackSecd.append(stackFirst[0])\n",
    "                    del stackFirst[0]\n",
    "            else:\n",
    "                stackSecd.append(s[i])\n",
    "            i += 1\n",
    "        \n",
    "        ans = \"\"\n",
    "        i = 0\n",
    "        while i < len(stackSecd):\n",
    "            ans += stackSecd[i]\n",
    "            i += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stack = []\n",
    "        word = ''\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                stack.append(word)\n",
    "                word = ''\n",
    "            elif c == ')':\n",
    "                word = stack.pop() + word[::-1]\n",
    "            else:\n",
    "                word += c\n",
    "        return word\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    obj = Solution()\n",
    "    s = \"(u(love)i)\"\n",
    "    print(obj.reverseParentheses(s))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stack = []\n",
    "        for ch in s:\n",
    "            if ch == \")\":\n",
    "                tmp = ''\n",
    "                while stack[-1] != '(':\n",
    "                    tmp += stack.pop()\n",
    "                stack.pop()\n",
    "                tmp = tmp[::-1]\n",
    "                stack += list(tmp[::-1])\n",
    "            else:\n",
    "                stack.append(ch)\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        m = s.count('(')\n",
    "        for i in range(m):\n",
    "            pattern = re.compile(r'\\(\\w*\\)')\n",
    "            a = pattern.findall(s)\n",
    "            new_s = re.sub(pattern,\"$$$\",s)\n",
    "            for k in a:\n",
    "                a = k.strip('()')\n",
    "                l = list(a)\n",
    "                new_a = \"\"\n",
    "                while len(l) > 0:\n",
    "                    new_a += l.pop()\n",
    "                new_s = new_s.split(\"$$$\")\n",
    "                new_s.insert(1,new_a)\n",
    "                n = new_s[0]+new_s[1]+new_s[2]\n",
    "                p = deque(new_s)\n",
    "                p.popleft()\n",
    "                p.popleft()\n",
    "                p.popleft()\n",
    "                p.appendleft(n)\n",
    "                new_s = '$$$'.join(p)\n",
    "                s = new_s\n",
    "                # s = new_s[0] + new_a + new_s[1]\n",
    "                # s = re.sub(\"\\$\\$\\$\",new_a,new_s)\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        while ')' in s:\n",
    "            end = s.index(')')\n",
    "            for i in range(end, -1, -1):\n",
    "                if s[i] == '(':\n",
    "                    #print(i)\n",
    "                    slice = s[end - 1:i:-1]  # not include ()\n",
    "                    #print(slice)\n",
    "                    s = s[:i] + slice + s[end + 1:]\n",
    "                    #print(s)\n",
    "                    break       \n",
    "        return s            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stack = []\n",
    "        word = ''\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                stack.append(word)\n",
    "                word = ''\n",
    "            elif c == ')':\n",
    "                word = stack.pop() + word[::-1]\n",
    "            else:\n",
    "                word += c\n",
    "        return word\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    obj = Solution()\n",
    "    s = \"(u(love)i)\"\n",
    "    print(obj.reverseParentheses(s))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stk = []\n",
    "        ans = ''\n",
    "        for ch in s:\n",
    "            if ch == \")\":\n",
    "                temp = ''\n",
    "                while stk and stk[-1] != \"(\":\n",
    "                    temp += stk.pop()\n",
    "                stk.pop()\n",
    "                \n",
    "                stk.extend(temp)\n",
    "            else:\n",
    "                stk.append(ch)\n",
    "        return \"\".join(stk)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "\n",
    "        stack = []\n",
    "\n",
    "        for i in s:\n",
    "            if i != ')':\n",
    "                stack.append(i)\n",
    "            elif i ==')':\n",
    "                tem =[]\n",
    "                while stack and stack[-1] !='(':\n",
    "                    tem.append(stack.pop())\n",
    "                if stack:\n",
    "                    stack.pop()\n",
    "                stack = stack+tem\n",
    "        return ''.join(stack)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ptn = re.compile(r\"\\((\\w*)\\)\")\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        while s.find('(') != -1: s = ptn.sub(lambda t: t.group(1)[::-1], s)\n",
    "        return s\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stack=[]\n",
    "        for i in s:\n",
    "            if i!=')':\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                x=''\n",
    "                while stack[-1]!='(':\n",
    "                    x=stack.pop()+x\n",
    "                stack.pop()\n",
    "                stack.append(x[::-1])\n",
    "        return ''.join(stack)\n",
    "                    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse_stack(self, stack):\n",
    "        ...\n",
    "        pop_item = stack.pop()\n",
    "        tmp_stack = []\n",
    "        while pop_item != \"(\":\n",
    "            tmp_stack.append(pop_item)\n",
    "            pop_item = stack.pop()\n",
    "        stack.extend(tmp_stack)\n",
    "        return stack\n",
    "\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stack = []\n",
    "        for single_s in s:\n",
    "            if single_s == \"(\":\n",
    "                stack.append(single_s)\n",
    "            elif single_s == \")\":\n",
    "                stack = self.reverse_stack(stack)\n",
    "            else:\n",
    "                stack.append(single_s)\n",
    "            # print(stack)\n",
    "\n",
    "        res = \"\".join(stack)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        if not str:\n",
    "            return str\n",
    "        tmpStack=[]\n",
    "        pos = [-1 for p in range(0,len(s)) ]\n",
    "        for i in range(0,len(s)):\n",
    "            if s[i] == '(':\n",
    "                tmpStack.append(i)\n",
    "            if s[i] == ')':\n",
    "                j = tmpStack.pop()\n",
    "                pos[i] = j\n",
    "                pos[j] = i\n",
    "\n",
    "        stp =1\n",
    "        idx=0\n",
    "        res=''\n",
    "        while idx < len(s):\n",
    "            if s[idx] == '(' or s[idx] == ')':\n",
    "                idx = pos[idx]\n",
    "                stp = - stp\n",
    "            else:\n",
    "                res += s[idx]\n",
    "            idx += stp\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        sum = 0\n",
    "        for i in s:\n",
    "            if i ==\"(\":\n",
    "                sum += 1\n",
    "\n",
    "        def change(s):\n",
    "            x = 0\n",
    "            for i in range(len(s)):\n",
    "                if s[i] == \"(\":\n",
    "                    if x == 0:\n",
    "                        l = i\n",
    "                    x += 1\n",
    "                    if x == 0:\n",
    "                        r = i\n",
    "                if s[i] == \")\":\n",
    "                    if x == 0:\n",
    "                        l = i\n",
    "                    x -= 1\n",
    "                    if x == 0:\n",
    "                        r = i\n",
    "            return s[0:l] + s[l + 1:r][::-1] + s[r + 1:]\n",
    "\n",
    "        for _ in range(sum):\n",
    "            s = change(s)\n",
    "        return s\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        stk = list()\n",
    "        ans = ''\n",
    "        for i in range(n):\n",
    "            if s[i] != ')':\n",
    "                stk.append(s[i])\n",
    "            elif s[i] == ')':\n",
    "                temp = []\n",
    "                while stk and stk[-1] != '(':\n",
    "                    temp.append(stk.pop())\n",
    "                if stk:\n",
    "                    stk.pop()\n",
    "                stk += temp\n",
    "        return \"\".join(stk)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        ans = \"\"\n",
    "        count = []\n",
    "        num = 0\n",
    "        for i in s:\n",
    "            if i.isalpha()==True and num == 0:\n",
    "                ans += i\n",
    "            elif i=='(':\n",
    "                count.append(\"\")\n",
    "                num += 1\n",
    "            elif i.isalpha()==True and num>0:\n",
    "                count[-1] += i\n",
    "            elif i==')':\n",
    "                num -= 1\n",
    "                if num == 0:\n",
    "                    ans += count[-1][::-1]\n",
    "                else:\n",
    "                    a = count.pop()[::-1]\n",
    "                    count[-1] += a  \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        ans = \"\"\n",
    "        count = []\n",
    "        num = 0\n",
    "        for i in s:\n",
    "            if i.isalpha()==True and num == 0:\n",
    "                ans += i\n",
    "            elif i=='(':\n",
    "                count.append(\"\")\n",
    "                num += 1\n",
    "            elif i.isalpha()==True and num>0:\n",
    "                count[-1] += i\n",
    "            elif i==')':\n",
    "                num -= 1\n",
    "                if num == 0:\n",
    "                    ans += count[-1][::-1]\n",
    "                else:\n",
    "                    a = count.pop()[::-1]\n",
    "                    count[-1] += a  \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if c != ')': stack.append(c) # 左括号or字母入栈\n",
    "            elif c == ')':\n",
    "                temp = [] # 临时列表 用于保存翻转后子串\n",
    "                while stack and stack[-1] != '(':\n",
    "                    temp.append(stack.pop())\n",
    "                stack.pop() # 左括号弹出\n",
    "                stack += temp # 接上temp，即内层翻转后的字符串\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        if not str:\n",
    "            return str\n",
    "        tmpStack=[]\n",
    "        pos = [-1 for p in range(0,len(s)) ]\n",
    "        for i in range(0,len(s)):\n",
    "            if s[i] == '(':\n",
    "                tmpStack.append(i)\n",
    "            if s[i] == ')':\n",
    "                j = tmpStack.pop()\n",
    "                pos[i] = j\n",
    "                pos[j] = i\n",
    "\n",
    "        stp =1\n",
    "        idx=0\n",
    "        res=''\n",
    "        while idx < len(s):\n",
    "            if s[idx] == '(' or s[idx] == ')':\n",
    "                idx = pos[idx]\n",
    "                stp = - stp\n",
    "            else:\n",
    "                res += s[idx]\n",
    "            idx += stp\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stack = []\n",
    "        for i in s:\n",
    "            if i != ')':\n",
    "                stack.append(i)\n",
    "            elif i == ')':\n",
    "                temp = []\n",
    "                while stack and stack[-1]!='(':\n",
    "                    temp.append(stack.pop())\n",
    "                if stack:\n",
    "                    stack.pop()\n",
    "                stack += temp\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        buff = []\n",
    "        for i in s:\n",
    "            if i == '(':\n",
    "                buff.append('')\n",
    "            elif i == ')':\n",
    "                a = buff.pop()\n",
    "                b = a[::-1]\n",
    "                if not buff:\n",
    "                    buff.append(b)\n",
    "                else:\n",
    "                    buff[-1] += b    \n",
    "            else:\n",
    "                if not buff:\n",
    "                    buff.append(i)\n",
    "                else:\n",
    "                    buff[-1] += i\n",
    "        \n",
    "        return buff[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stack = []\n",
    "\n",
    "        for elem in s:\n",
    "            if elem == \")\":\n",
    "                cur = []\n",
    "                while stack and stack[-1]!=\"(\":\n",
    "                    cur.append(stack.pop())\n",
    "                stack.pop()\n",
    "                stack = stack + cur \n",
    "            else:\n",
    "                stack.append(elem)\n",
    "\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stack = []\n",
    "        pair = [0] * len(s)\n",
    "        # record the position of each pair of p\n",
    "        for i, c in enumerate(s):\n",
    "            if c == '(':\n",
    "                stack.append(i)\n",
    "            elif c == ')':\n",
    "                left_pair = stack.pop()\n",
    "                pair[left_pair] = i\n",
    "                pair[i] = left_pair\n",
    "        \n",
    "        # iterate through the string for answer\n",
    "        result = ''\n",
    "        dir = 1\n",
    "        index = 0\n",
    "        while(index < len(s)):\n",
    "            if s[index] == '(' or s[index] == ')':\n",
    "                index = pair[index]\n",
    "                dir = -dir\n",
    "            else:\n",
    "                result += s[index]\n",
    "            index += dir\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def reverseParentheses(self, s: str) -> str:\r\n",
    "        st = []\r\n",
    "        for i in range(len(s)):\r\n",
    "            if s[i] != ')':\r\n",
    "                st.append(s[i])\r\n",
    "                continue\r\n",
    "            t = []\r\n",
    "            while \"(\" != (c:=st.pop()):\r\n",
    "                t.append(c)\r\n",
    "            for c in t:\r\n",
    "                st.append(c)\r\n",
    "        return \"\".join(st)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def reverseParentheses(self, s: str) -> str:\r\n",
    "        stack = list()\r\n",
    "        for c in s:\r\n",
    "            if c == ')':\r\n",
    "                temp = list()\r\n",
    "                while stack and stack[-1] != '(':\r\n",
    "                    temp.append(stack.pop())\r\n",
    "                stack.pop()\r\n",
    "                stack.extend(temp)\r\n",
    "            else:\r\n",
    "                stack.append(c)\r\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        stack = []\n",
    "        n = len(s)\n",
    "        pair = [0] * n\n",
    "\n",
    "        # 预先存储左右括号的映射关系\n",
    "        for i in range(n):\n",
    "            if s[i] == '(':\n",
    "                stack.append(i)\n",
    "            if s[i] == ')':\n",
    "                j = stack.pop()\n",
    "                pair[i] = j\n",
    "                pair[j] = i \n",
    "        \n",
    "        index = 0\n",
    "        # step = 1 表示向右走, step = -1 表示向左走\n",
    "        step = 1\n",
    "        result = []\n",
    "        while index < n:\n",
    "            if pair[index]:\n",
    "                index = pair[index]\n",
    "                # 走的方向反转\n",
    "                step = -step\n",
    "            else:\n",
    "                result.append(s[index])\n",
    "            index += step\n",
    "        return \"\".join(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseParentheses(self, s: str) -> str:\n",
    "        if not s:\n",
    "            return \n",
    "        stack = []\n",
    "        res = ''\n",
    "        for c in s:\n",
    "            temp = ''\n",
    "            if c != ')':\n",
    "                stack.append(c)\n",
    "            else:\n",
    "                while stack[-1] != '(':\n",
    "                    temp += stack.pop()[::-1]\n",
    "                stack.pop()\n",
    "                stack.append(temp)\n",
    "                temp = ''\n",
    "        while stack:\n",
    "            res += stack.pop(0)\n",
    "        return res\n",
    "\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
